'''
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
'''
class ListNode:
    #定义一个节点类
    def __init__(self, x,next=None):
        self.val = x
        self.next = next
class Solution():

    def merge_two_sortedlist(self, l1, l2):
        #设置一个哨兵节点
        head = ListNode(0)
        #用来链接新链表
        cur = head
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        #将非空的链表链接到新链表之后
        if l1:
            cur.next = l1
        elif l2:
            cur.next = l2
        return head.next
#示例
if __name__ == '__main__':
    l1 = ListNode(1)
    l1.next = ListNode(2)
    l1.next.next = ListNode(3)
    l1.next.next.next = ListNode(5)
    l2 = ListNode(1)
    l2.next = ListNode(3)
    l2.next.next = ListNode(4)
    s = Solution()
    lst = s.merge_two_sortedlist(l1, l2)
    while lst:
        print(lst.val,end=' ')
        lst = lst.next
